package name.huzhenbo.java.algorithm.matrix;

class SparseMatrix {
    private static final int MAX_SIZE = 20;
    private int x;
    private int y;
    private int length;
    private int[][] holder;

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }

    public int getLength() {
        return length;
    }

    public void setLength(int length) {
        this.length = length;
    }

    public SparseMatrix(int x, int y) {
        this.x = x;
        this.y = y;
        length = 0;
        holder = new int[MAX_SIZE][3];
    }

    public void add(int x, int y, int value) {
        holder[length] = new int[]{x, y, value};
        length++;
    }

    public SparseMatrix transpose() {
        SparseMatrix sm = new SparseMatrix(y, x);
        sm.setLength(length);
        // [2, 4] means this row has 2 items, and current position is 4
        int[][] positions = new int[y][2];
        // count the number of each row
        for(int i = 0; i < length; i++){
            positions[holder[i][1]][0]++;
        }
        // set the start position of each row
        int start = 0;
        positions[0][1] = start;
        for(int i = 1; i < positions.length; i++){
            start += positions[i - 1][0];
            positions[i][1] = start;
        }
        // insert
        for(int i = 0; i < length; i++){
            int insertPosition = positions[holder[i][1]][1]++;
            sm.holder[insertPosition] = new int[]{holder[i][1], holder[i][0], holder[i][2]};
        }
        return sm;
    }

    public int[] get(int i) {
        return holder[i];
    }

    public SparseMatrix multi(SparseMatrix another) {
        SparseMatrix sm = new SparseMatrix(x, another.y);
        for(int i = 0; i < length; i++){
            for(int j = 0; j < another.length; j++){
                if(holder[i][1] == another.holder[j][0]){
                    sm.add(holder[i][0], another.holder[j][1], holder[i][2] * another.holder[j][2]);
                }
            }
        }
        return sm;
    }
}
